package inset;

import java.util.*;

import org.jgrapht.*;
import org.jgrapht.traverse.*;


/**
 * Performs cycle detection on a graph. The <i>inspected graph</i> is specified
 * at construction time and cannot be modified. Currently, the detector supports
 * only directed graphs.
 *
 * @author John V. Sichi
 * @since Sept 16, 2004
 */
public class CycleDetector<V, E>
{

    //~ Instance fields -------------------------------------------------------

    /**
     * Graph on which cycle detection is being performed.
     */
    Graph<V, E> graph;

    //~ Constructors ----------------------------------------------------------

    /**
     * Creates a cycle detector for the specified graph.  Currently only
     * directed graphs are supported.
     *
     * @param graph the DirectedGraph in which to detect cycles
     */
    public CycleDetector(DirectedGraph<V, E> graph)
    {
        this.graph = graph;
    }

    //~ Methods ---------------------------------------------------------------

    /**
     * Performs yes/no cycle detection on the entire graph.
     *
     * @return true iff the graph contains at least one cycle
     */
    public boolean detectCycles()
    {
        try {
            execute(null, null);
        } catch (CycleDetectedException ex) {
            return true;
        }

        return false;
    }

    /**
     * Performs yes/no cycle detection on an individual vertex.
     *
     * @param v the vertex to test
     *
     * @return true if v is on at least one cycle
     */
    public boolean detectCyclesContainingVertex(V v)
    {
        try {
            execute(null, v);
        } catch (CycleDetectedException ex) {
            return true;
        }

        return false;
    }

    /**
     * Finds the vertex set for the subgraph of all cycles.
     *
     * @return set of all vertices which participate in at least one cycle in
     *         this graph
     */
    public List<List<V>> findCycles()
    {	
	ArrayList<List<V>> cycles = new ArrayList<List<V>>();
        execute(cycles, null);

        return cycles;
    }

    /**
     * Finds the vertex set for the subgraph of all cycles which contain a
     * particular vertex.
     *
     * @param v the vertex to test
     *
     * @return set of all vertices reachable from v via at least one cycle
     */
    public List<List<V>> findCyclesContainingVertex(V v)
    {
        ArrayList<List<V>> cycles = new ArrayList<List<V>>();
        execute(cycles, v);

        return cycles;
    }

    private void execute(List<List<V>> s, V v)
    {
        ProbeIterator iter = new ProbeIterator(s, v);

        while (iter.hasNext()) {
            iter.next();
        }
    }

    //~ Inner Classes ---------------------------------------------------------

    /**
     * Exception thrown internally when a cycle is detected during a yes/no
     * cycle test.  Must be caught by top-level detection method.
     */
    private static class CycleDetectedException
        extends RuntimeException
    {
        private static final long serialVersionUID = 3834305137802950712L;
    }

    /**
     * Version of DFS which maintains a backtracking path used to probe for
     * cycles.
     */
    private class ProbeIterator
        extends DepthFirstIterator<V, E>
    {
        private List<V> path;        
        private List<List<V>> cycleList;

        ProbeIterator(List<List<V>> cycleList, V startVertex)
        {
            super(graph, startVertex);            
            this.cycleList = cycleList;
            path = new ArrayList<V>();
        }

        /**
         * {@inheritDoc}
         */
        protected void encounterVertexAgain(V vertex, E edge)
        {
            super.encounterVertexAgain(vertex, edge);

            int i = path.indexOf(vertex);

            if (i > -1) {
                if (cycleList == null) {
                    // we're doing yes/no cycle detection
                    throw new CycleDetectedException();
                }

                ArrayList<V> lst = new ArrayList<V>();
                cycleList.add(lst);
                for (; i < path.size(); ++i)
                {                    
                    lst.add(path.get(i));
                }
            }
        }

        /**
         * {@inheritDoc}
         */
        protected V provideNextVertex()
        {
            V v = super.provideNextVertex();

            // backtrack
            for (int i = path.size() - 1; i >= 0; --i) {
                if (graph.containsEdge(path.get(i), v)) {
                    break;
                }

                path.remove(i);
            }

            path.add(v);

            return v;
        }
    }
}
